One known way of storing data is in the form of a linked list. A linked list enables the dynamic storage of uniform or non-uniform data items. A number of related data items can be contained within a single list, with each item being linked to the next in the list by a pointer field. This is essentially a software process. The pointer field enables the list to be traversed and the data accessed. In its simplest form new items are always added to the bottom of the list and old items are always removed from the top of the list. A common example of this is a FIFO device. Updating this type of list requires the operations of list concatenation and item removal. One example of an application in which this type of list is used is in the queuing of tasks within an operating system, with tasks being scheduled purely according to their arrival time.
A more complex use of a linked list allows for the ordering of all or part of the data information within the list. Updating this type of list requires the ability to add new items or delete existing items at arbitrary positions within the list. Examples of applications in which this type of list is used include the configuration of routing tables, call records, and translation tables in telecommunications systems and the scheduling of tasks, by priority, in computer operating systems. U.S. Pat. No. 5,274,768 (Traw et al.) describes an interface for Asynchronous Transfer Mode (ATM) networks which uses this kind of linked list manager.
An example of this type of list is shown in FIG. 1. A memory 30 has a plurality of memory locations, which are numbered 1 to 20. A reserved part of the memory, such as location 1, holds a pointer start_ptr to the memory location of the first element in the list. In this example the first element in the list occupies memory location 4. It could however occupy any one of the memory locations. An enlargement shows the contents of memory location 4 in more detail. A data item DATA and a pointer ptr_next are stored at this memory location. The pointer points to the memory location of the next element in the linked list. This has a value "16" which is the memory location where the second element in the list is stored. The memory holds a number of similar elements which are linked to one another in this manner.
The process for updating this type of list will now be described with reference to FIGS. 1A to 1C. FIG. 1A shows two elements, one stored at memory location 4, and a second at memory location 9. The pointer of the element at location 4 points to the memory location 9.
Firstly, the situation where a new element needs to be added to the list is considered. The new element is inserted at an available location in the memory. This is location 16. The element must be tied into the list at the required point. FIG. 1B shows the result of adding this new element to the list between the two existing elements. The pointer value of the element held at memory location 4 now points to memory location 16, and the pointer value of the newly inserted element points to memory location 9.
Secondly, the situation where an existing element needs to be deleted from the list is considered. The existing element at memory location 16 needs to be removed from the list. The pointer value of the element held at location 4 is changed to point to the memory location of the element following the one to be deleted i.e. the element at location 9.
A problem associated with linked lists is that in order to find a particular data item the list must be searched in a systematic manner, beginning at the first element in the list and continuing through the list until the item is found. This makes the search process slow. To improve the access process, doubly linked lists are also commonly used. In a doubly linked list, for each data item, pointers are used to indicate both the next element in the list and the previous item in the list. In this manner the list may be traversed in either direction.
The use of linked lists and doubly-linked lists has a number of problems. Firstly the process of configuring and maintaining the lists is complex and thus necessitates its implementation using software. This precludes their use for real-time, high throughput applications. Secondly, the task of updating the linked lists usually requires that the process of accessing the data is interrupted. Thirdly, there is a need to store both the data elements and the pointers which link the elements together.
One known method for updating data lists within real-time hardware systems involves the use of a shadow memory. Firstly, an updated list is configured within the shadow memory and then, secondly, this is swapped with the original memory to complete the update process. Using a shadow memory has a disadvantage of requiring a doubling of the overall memory requirement. It is therefore a particularly expensive option for very high speed real-time applications which demand expensive, high-performance memory devices.
Both of these techniques have undesirable attributes, particularly for use in real-time applications.
The present invention seeks to provide an improved method of updating a data table or list which minimises the disadvantages of the prior art methods.